암달의 법칙

Amdahl's law

컴퓨터 공학 분야의 법칙.

어떤 작업의 시간 효율을 개선할 때, 전체 작업시간에 대해 P만큼의 작업시간을 차지하는 작업의 효율을 S만큼 향상시켰다 가정하자. 그렇다면 전체 작업 효율은 다음과 같이 향상된다.
$\displaystyle \frac{1}{(1-P)+\frac{P}{S}}$

가령, 전체 작업 시간 중에 10%를 차지하는 작업의 속도를 2배 증가시켰다면, 전체 작업 속도는 약 1.05배로 증가한다.
$\displaystyle \frac{1}{(1-0.1)+\frac{0.1}{2}} = \frac{1}{0.95} \fallingdotseq 1.05$

다음과 같은 의미를 지닌다. 첫째로, 전체 작업의 효율을 최대한 증가시키고 싶다면 그 중에 가장 비중이 큰 작업부터 초점을 맞추는 것이 좋다. 둘째로, 일부 작업들이 더 이상 개선의 여지가 없을 경우 전체 작업이 최대 어느정도의 개선 효율을 보일 수 있는지에 대해 예측이 가능하다.[1]

2010년도의 개인 사용자가 가장 쉽게 이 법칙을 느낄 수 있는 것이 바로 SSD. 보조 기억 장치의 처리 시간은 다른 자원에 비해서 자릿수가 다른 수준으로 느리다. 그렇기 때문에 사용자 응답 시간의 대부분을 저장 장치 속도가 결정하는데 이를 HDD에서 SSD로 바꿔주는 것으로 CPU나 메모리 업그레이드와는 차원이 다른 성능 향상을 체감할 수 있다.

파일:external/upload.wikimedia.org/500px-AmdahlsLaw.svg.png
병렬 컴퓨팅을 할 경우, 일부 병렬화 가능한 작업들은 사실상 계산에 참여하는 컴퓨터의 개수에 비례해서 속도가 늘어난다. 이러한 경우 암달의 법칙에 의해서 전체 수행시간의 개선 효과는 병렬화가 불가능한 작업들의 비중에 크게 영향을 받게 된다. 즉, 아무리 컴퓨터의 개수가 늘어나더라도 위의 그림에서 보는 것 처럼 속도의 한계는 정해져있다는 것.

위에서 서술했듯이, 이 법칙에 의해서 수행 속도의 한계가 정해져버리기 때문에, 이 법칙을 암달의 저주라고 부르기도 한다. 엄밀히 말해 암달은 "그렇다"는 사실을 말했을 뿐이지 암달이 컴퓨터 공학에 제약을 건 것은 아니기 때문에 저주라는 별칭은 억울하겠지만 (…)

암달의 법칙과는 다르다. 암달의 법칙이 실행 시간의 감소에 초점을 두었다면 구스타프슨의 법칙은 동일한 시간 동안의 작업분량에 초점을 두었다.
즉, 암달의 법칙은 latency에, 구스타프슨의 법칙은 throughput에 기준을 두었다고 보면 된다.
아래와 같은 수식으로 표현된다.
$\displaystyle S(P)=P - a(P - 1)$
여기에서 $P$는 프로세서의 개수, $a$는 병렬화되지 않는 부분의 비율, $S(P)$는 이론상 성능 향상 비율이다. 여기에서의 성능 향상은 같은 시간 동안 처리하는 데이터량의 비율이다.

파일:external/upload.wikimedia.org/Gustafson.png

가령 병렬화되지 않는 부분이 전체 프로세스의 50%이고 CPU를 128개 투입한다면 성능 향상은 $128 - 0.5 * (128 - 1) = 64.5$이다. 즉 같은 시간 동안 128개의 CPU를 활용해서 64.5배의 데이터를 처리할 수 있게 된다.